#include <cstdlib>
#include <iostream>
#include <ctime>
#include "grafo.h"
#include "exacto.h"

using namespace std;

class Grafo leerInput(istream&);
void escribirOutput(ostream&, const set<uint>&);
timespec diff(timespec start, timespec end);

Grafo leerInput(istream& is, bool& procesar) {
	uint n, m;
	is >> n;

	if (n != 0) {
		is >> m;		
	} else {
		procesar = false;
		m = 0;
	}
	
	Grafo grafo(n);
	for (int k=0; k < m; k++) {
		uint i, j;
		is >> i >> j;
		grafo.agregarArista(i,j);
	}
	
	return grafo;
}

ostream& operator<<(ostream &os, set<uint> &solucion) {
	for(set<uint>::iterator it = solucion.begin(); it != solucion.end(); it++)
		os << (*it) << " ";
	os << endl;
	return os;
}

int main() {
	bool procesar = true;
	
	while (true) {
		
		#ifdef TESTING
			timespec start, end, result;
			clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
		#endif
		
		Grafo grafo = leerInput(cin, procesar);
		if (!procesar)
			break;		
		
		CliqueMaximaFronteraExacto* iniciar;
		
		iniciar = new CliqueMaximaFronteraExacto(grafo);
		
		uint cant;
		set<uint> solucion = iniciar->resolver(cant);

		#ifdef TESTING
			clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
			result = diff(start, end);
			cout << result.tv_sec * (unsigned long) 1000000000 + result.tv_nsec << endl;
		#endif

		#ifndef TESTING
			cout << cant << " " << solucion.size() << " ";
			cout << solucion;
		#endif
	}
	
	return 0;
}

timespec diff(timespec start, timespec end) {
	timespec temp;
	if((end.tv_nsec - start.tv_nsec) < 0) {
		temp.tv_sec = end.tv_sec - start.tv_sec - 1;
		temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
	} else	{
		temp.tv_sec = end.tv_sec - start.tv_sec;
		temp.tv_nsec = end.tv_nsec - start.tv_nsec;
	}
	return temp;
}
